Queue structures may be used for workflows, such as producer-consumer workflows, to queue tasks or messages provided, or acted upon, by different participants or users (e.g., application components or other software entities) of the workflow. For example, a first software entity may enqueue a message in a queue that is subsequently, within an expiry time of the message, dequeued by a second software entity and acted upon for purposes of the workflow. Dequeue commands for these queues may result in significant latency when many messages have expired. That is, each dequeue request may move a queue header cursor in a nested table forward through each entry in the queue until the header cursor reaches the end of the queue or the first non-expired message in the queue.
In some queue structures, a garbage collection mechanism may be utilized to clear expired queue tasks or messages to reduce the latency of searching over large numbers of expired queue tasks or messages. In cases where thousands or millions of expired tasks or messages remain queued, garbage collection is unable to perform a cleanup of the expired entries at a rate that prevents system time-outs or conflicts for extended dequeue searches of the queue structure.